#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int g[10][10], ans, T, path[111], p[10], pid, vis[10], n;
void dfs(int i, int cnt, int cost) {
    if(cnt == n) {
        if(cost+g[i][0] < ans) {
            ans = cost + g[i][0];
            pid = 0;
            for(int j = 0; j < n; j++) path[pid++] = p[j];
        } else if(cost+g[i][0] == ans && pid < n*10) for(int j = 0; j < n; j++) path[pid++] = p[j];
        return;
    }
    for(int j = 1; j <= n; j++) {
        if(!vis[j]) {
            vis[j] = true;
            p[cnt] = j;
            dfs(j, cnt+1, cost+g[i][j]);
            vis[j] = false;
        }
    }
}
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) scanf("%d", &g[i][j]);
        ans = 11111, pid = 0;
        memset(vis, false, sizeof(vis));
        dfs(0,0,0);
        printf("%d\n", ans);
        pid = min(pid, n*10);
        for(int i = 0; i < pid; i += n) {
            for(int j = i; j < i+n; j++) {
                if(j%n) putchar(' ');
                printf("%d", path[j]);
            }
            puts("");
        }
    }
    return 0;
}
